/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

/**
 * @author : sunzb
 * @date: 2019/5/15
 */
// ?_? 牛顿迭代法
public class _21_69_SqrtX {

    /*public double mySqrt4(int x) {
        double xhalf = 0.5 * x ;
        int i = 0x5f3759df - (x >> 1);
        double d = i;
        d = d * (1.5 - xhalf * d * d);
        return d;
    }*/

    double result = 0;

    public double mySqrt3(int x) {

        if (x == 0 || x == 1) return x;
        dg(x, x);
        if (Math.ceil(result) - result < 1e-7) return (int) Math.ceil(result);
        else return (int) result;
//        return r;
    }

    public void dg(double r, int x) {
        if (r <= x / r) {
            if (Math.ceil(r) - r < 1e-7) result = Math.ceil(r);
            else result = r;
        } else {
            double temp = (r + x / r) / 2;
            if (r == temp) {
                result = r;
                return;
            }
            dg(temp, x);
        }
    }

    public double mySqrt2(int x) {
        double r = x;
        while (r > x / r) {
            double temp = (r + x / r) / 2;
            if (r == temp) break;
            r = temp;
        }
        if (Math.ceil(r) - r < 1e-7) return (int) Math.ceil(r);
        else return (int) r;
//        return r;
    }

    public double mySqrt1(int x) {
        if (x == 0 || x == 1) return x;
        double left = 1;
        double right = x;
        while (left <= right) {
            double mid = left + (right - left) / 2;
            // x * x 会越界
            double value =  x / mid - mid;
            if (right - left < 1e-7 || Math.abs(value) < 1e-10) {
                if (Math.ceil(mid) - mid < 1e-7) return (int) Math.ceil(mid);
                else return (int) mid;
//                return mid;
            }
            if (value > 0) left = mid;
            else right = mid;
        }
        return 0;
    }

    public int mySqrt(int x) {
        return (int) Math.sqrt(x);
    }

    public static void main(String[] args) {
        System.out.println(new _21_69_SqrtX().mySqrt2(4));
        System.out.println(new _21_69_SqrtX().mySqrt2(2147395599));
        System.out.println(new _21_69_SqrtX().mySqrt2(7));
        System.out.println(new _21_69_SqrtX().mySqrt3(4));
        System.out.println(new _21_69_SqrtX().mySqrt3(2147395599));
        System.out.println(new _21_69_SqrtX().mySqrt3(7));
    }
}
